翻訳と辞書 Words near each other ・ Zemlyanoy Gorod ・ Zemlyanskiy ・ Zemmer ・ Zemmix ・ Zemmoura ・ Zemmoura District ・ Zemmouri ・ Zemnick ・ Zemné ・ Zemo barony ・ Zemo-Achabeti ・ Zemo-Koshka ・ Zemo-Monasteri ・ Zemongo Faunal Reserve ・ Zemono ・ Zemor's decoding algorithm ・ Zempassogo ・ Zempin ・ Zemple, Minnesota ・ Zemplén ・ Zemplén County ・ Zemplén Mountains ・ Zemplénagárd ・ Zemplín ・ Zemplín (region) ・ Zemplín (village) ・ Zemplín Castle ・ Zemplín Mountains ・ Zemplínska ・ Zemplínska Nová Ves Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Zemor's decoding algorithm ： ウィキペディア英語版 Zemor's decoding algorithm In coding theory, Zemor's algorithm, designed and developed by Gilles Zemor,〔(Gilles Zemor )〕 is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of Sipser and Spielman. Zemor considered a typical class of Sipser–Spielman construction of expander codes, where the underlying graph is bipartite graph. Sipser and Spielman introduced a constructive family of asymptotically good linear-error codes together with a simple parallel algorithm that will always remove a constant fraction of errors. The article is based on Dr. Venkatesan Guruswami's course notes 〔http://www.cs.washington.edu/education/courses/cse590vg/03wi/scribes/1-27.ps〕 == Code construction == Zemor's algorithm is based on a type of expander graphs called Tanner graph. The construction of code was first proposed by Tanner.〔http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture14.pdf〕 The codes are based on double cover $d$, regular expander $G$, which is a bipartite graph. $G$ =$\backslash left(V,E\backslash right)$, where $V$ is the set of vertices and $E$ is the set of edges and $V$ = $A$ $\backslash cup$ $B$ and $A$ $\backslash cap$ $B$ = $\backslash emptyset$, where $A$ and $B$ denotes the set of 2 vertices. Let $n$ be the number of vertices in each group, ''i.e'', $|A|\; =|B|\; =n$. The edge set $E$ be of size $N$ =$nd$ and every edge in $E$ has one endpoint in both $A$ and $B$. $E(v)$ denotes the set of edges containing $v$. Assume an ordering on $V$, therefore ordering will be done on every edges of $E(v)$ for every $v\; \backslash in\; V$. Let finite field $\backslash mathbb=GF(2)$, and for a word $x=(x\_e),\; e\backslash in\; E$ in $\backslash mathbb^N$, let the subword of the word will be indexed by $E(v)$. Let that word be denoted by $(x)\_v$. The subset of vertices $A$ and $B$ induces every word $x\backslash in\; \backslash mathbb^N$ a partition into $n$ non-overlapping sub-words $\backslash left(x\backslash right)\_v\backslash in\; \backslash mathbb^d$, where $v$ ranges over the elements of $A$. For constructing a code $C$, consider a linear subcode $C\_o$, which is a $()$ code, where $q$, the size of the alphabet is $2$. For any vertex $v\; \backslash in\; V$, let $v(1),\; v(2),\backslash ldots,v(d)$ be some ordering of the $d$ vertices of $E$ adjacent to $v$. In this code, each bit $x\_e$ is linked with an edge $e$ of $E$. We can define the code $C$ to be the set of binary vectors $x\; =\; \backslash left(\; x\_1,x\_2,\backslash ldots,x\_N\; \backslash right)$ of $\backslash ^N$ such that, for every vertex $v$ of $V$, $\backslash left(x\_,\; x\_,\backslash ldots,\; x\_\backslash right)$ is a code word of $C\_o$. In this case, we can consider a special case when every vertex of $E$ is adjacent to exactly $2$ vertices of $V$. It means that $V$ and $E$ make up, respectively, the vertex set and edge set of $d$ regular graph $G$. Let us call the code $C$ constructed in this way as $\backslash left(G,C\_o\backslash right)$ code. For a given graph $G$ and a given code $C\_o$, there are several $\backslash left(G,C\_o\backslash right)$ codes as there are different ways of ordering edges incident to a given vertex $v$, i.e., $v(1),\; v(2),\backslash ldots,v(d)$. In fact our code $C$ consist of all codewords such that $x\_v\backslash in\; C\_o$ for all $v\; \backslash in\; A,\; B$. The code $C$ is linear $()$ in $\backslash mathbb$ as it is generated from a subcode $C\_o$, which is linear. The code $C$ is defined as $C=\backslash$ for every $v\backslash in\; V$. In this figure, $(x)\_v\; =\backslash left(x\_,\; x\_,\; x\_,\; x\_\backslash right)\backslash in\; C\_o$. It shows the graph $G$ and code $C$. In matrix $G$, let $\backslash lambda$ is equal to the second largest eigen value of adjacency matrix of $G$. Here the largest eigen value is $d$. Two important claims are made: 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Zemor's decoding algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.